package algorithm.middle;

import pojo.TreeNode;

import java.util.Arrays;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: BuildTree07
 * @description: 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 *
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 *
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/2416:17
 * @since V1.0 重建二叉树
 */
public class BuildTree07 {

    public static void main(String[] args) {
        int[] ints = {0, 1};
        int[] ints1 = Arrays.copyOfRange(ints, 1, 1);
        System.out.println(Arrays.toString(ints1));
    }
    /**
     * 前序遍历的首元素 为 树的根节点 node 的值。
     * 在中序遍历中搜索根节点 node 的索引 ，可将 中序遍历 划分为 [ 左子树 | 根节点 | 右子树 ] 。
     * 根据中序遍历中的左 / 右子树的节点数量，可将 前序遍历 划分为 [ 根节点 | 左子树 | 右子树 ] 。
     *
     *[一,2,4,5,3,6,7] [4.2.5.一.6.3.7]        一
     * [二,4,5] [4,二,5]  [三,6,7] [6,三,7]  二   三
     *
     * 作者：jyd
     * 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length==0){
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[0]);
        fun(treeNode,preorder,inorder);
        return treeNode;
    }
    //递归
    public void fun(TreeNode tempRoot,int[] preorder, int[] inorder) {
        if (preorder.length<=1) return;
        if (inorder.length<=1) return;
        int k=0;
        for (int i=0;i<inorder.length;i++){
            if (inorder[i]==tempRoot.val){
                k=i;
                break;
            }
        }
        int[] leftPre = Arrays.copyOfRange(preorder, 1, 1 + k);
        int[] leftIn = Arrays.copyOfRange(inorder, 0, k);
        int[] rightPre = Arrays.copyOfRange(preorder, 1+k, preorder.length);
        int[] rightIn = Arrays.copyOfRange(inorder, 1+k, inorder.length);
        if (leftPre.length!=0){
            TreeNode leftNode = new TreeNode(leftPre[0]);
            tempRoot.left = leftNode;
            fun(leftNode,leftPre,leftIn);
        }
        if (rightPre.length!=0){
            TreeNode rightNode = new TreeNode(rightPre[0]);
            tempRoot.right = rightNode;
            fun(rightNode,rightPre,rightIn);
        }
    }
}
